1. Field of the Invention
This invention pertains generally to digital circuit design and particularly to logic synthesis and more particularly to a technology mapper used to perform logic synthesis.
2. Background of the Invention
Modem logic circuits are so complex that circuit designers must use computer-based techniques to help them in their task. The designers first abstractly represent the circuit as multiple combinatorial blocks (e.g., single-output, multiple-input Boolean equations) separated by sequential states. The combinatorial blocks are described by Directed Acyclic Graphs (xe2x80x9cDAGsxe2x80x9d) also referred to as xe2x80x9cBoolean Trees.xe2x80x9d In general, the computer-based techniques transform the abstract representation of the circuit design into a technology-dependent netlist representing the same circuit design. Computer-based techniques including behavioral synthesis, floorplanning, and logic synthesis are used to perform this transformation.
Logic synthesis takes the abstract representation of the circuit design, performs some abstract optimizations on the combinatorial and sequential blocks, and maps the blocks to the target technology library. Logic synthesis uses a technique called xe2x80x9cTechnology Mappingxe2x80x9d to map the combinatorial blocks of the Boolean tree into the target library by replacing the nodes with library cells.
The Technology Mapper, accordingly, should efficiently tile a DAG with library cells. Usually, the task of matching the Boolean equation of a sub-part of the DAG to a cell is passed off to another entity, called the xe2x80x9cBoolean Matcher.xe2x80x9d The Boolean Matcher accepts a father node, some child nodes, and a library cell, and determines if the cell can cover the group of nodes. That is, the Boolean Matcher determines whether the cell has the same equation as a sub-part of the DAG, or the inverted equation modulo the inversion of any input. If the cell has the same equation as a sub-part of the DAG, the Boolean Matcher produces the input correspondence, which associates each cell input to an input of a node and states the cell""s input""s polarity.
The difficulty in performing Boolean matching lies in the possible permutation of inputs. A Boolean Matcher must be able to find not only an equivalent cell, but also the input correspondence. Thus, the representation of the equations for the DAG and the cell must conveniently allow inputs of at least one equation to be swapped in order to test the equivalence for any given pin permutation.
To this end, many techniques have been developed for performing Boolean matching. Some techniques perform matching based on tree patterns. Before starting a mapping process, the library cells are parsed and patterns are stored which represent the function implemented by each cell. Then, the Matcher essentially matches the current sub-tree function with a pattern. To allow the mapper to find better solutions, the matcher tests the equivalence of the cell pattern and the sub-tree function modulo the inversion of the function inputs and modulo the inversion of the function.
One reference,. Kurt Keutzer, xe2x80x9cDAGON: Technology Binding and Local Optimization by DAG Matching,xe2x80x9d Proceedings of the 24th ACM/IEEE Design Automation Conference, 1987, introduces a formalism for technology mapping using DAGs. The matching is performed by matching technology patterns in the canonical NAND/NOT form, thereby allowing matching modulo the polarity of inputs. However, this technique requires the Boolean network to be prepared before matching by covering it with virtual NAND/NOT cells. In addition, one has to write the patterns of the library cells in NAND/NOT form in order to map onto a technology library.
Another technique, described in E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, A. Wang, xe2x80x9cTechnology Mapping in MIS,xe2x80x9d Proceedings of the ICCAD, 1987, also uses Boolean matching. This technique creates all non-isomorphic and irredundant NAND/NOT-based graphs. For each graph, an automaton is generated that does a depth-first transversal of the graph. The Boolean network is transformed into NAND/NOT graphs, and the match is tested by the automaton trying to transverse the Boolean network graph. A problem with this technique is that it must try several matches on the same cell. For instance, on an AND4 cell, two automata are used, one for the balanced graph and one for the unbalanced graph.
In F. Mailhot, G. De Michelli, xe2x80x9cTechnology Mapping using Boolean Matching,xe2x80x9d Proceedings of the European Conference on Design Automation, 1990, the authors focus on symmetry between inputs to rapidly eliminate non-matching cases. For instance, when matching an AND2 (s=a AND b) gate, the two inputs can be marked as symmetric. Thus, if a Boolean equation F(x, y) is matched with {x=a, y=b} with a certain polarity for x and y, F(x, y) is also matched with {x=b, y=a} with the same polarities. On the contrary, it is useless to test the matching with {x=b, y=a} if the matching {x=a, y=b} has already been checked and found not feasible. This technique greatly limits the search space for symmetric cells (and library cells are often symmetric). But for all possible permutation of inputs, the technique must re-do the Shannon decomposition following the input permutation ordering.
Accordingly, there is a need for a technology mapper that does not have the deficiencies of the above-described techniques.
The above needs are met by a method and system for technology mapping that compares signatures of truth tables to determine whether part of a combinatorial block matches a technology cell. A preferred embodiment of the present invention accepts a Boolean tree describing the function of all or part of the combinatorial block and a cell of a technology library in the form of a string describing the function of the cell. The string is parsed to generate a Boolean tree describing the function of the library cell.
First and second truth tables are respectively generated from the Boolean tree representing the portion of the combinatorial block and the Boolean tree describing the function of the cell. Each truth table includes one or more inputs representing the one or more inputs to the nodes of the Boolean tree from which the truth table was generated. In addition, each truth table includes a signature describing the output of the Boolean tree from which the truth table was generated. Due to the nature of truth tables, a truth table representing the function of a combinatorial block or library cell can be described as a pair {I, S}, where I is an ordered list of the inputs and S is a signature such as an integer representing the output column of the truth table in decimal notation.
If the first and second truth tables match, then the portion of the combinatorial lock and the library cell described by the first and second truth tables also match. Two truth tables may match if the truth tables have the same number of inputs. Therefore, a referred embodiment of the present invention compares the two ordered lists of inputs to determine whether each list includes the same number of inputs. In addition, two truth tables having the same number of inputs match if the signatures of the truth tables also match. Accordingly, if each truth table has the same number of inputs, the signatures of the two truth tables are compared to determine whether the truth tables match, i.e., represent the same function.
If the signatures of the truth tables do not match, then it is possible that the signatures will match if the order of the inputs to the first or second truth tables is permuted. When generating the truth table representing the library cell, therefore, a preferred embodiment of the present invention also generates truth tables representing the cells having permutations of the inputs of the library cell. While there may be a large number of permutations, many cells have symmetric pins, which reduces the number of unique permutations. The truth table representing the portion of the combinatorial block is compared against all of the truth tables representing permutations of the inputs of the library cell to determine whether the signatures match.
In addition, the signatures of the truth tables may match if the output column of one of the truth tables is inverted. This inversion is represented by performing a logic NOT on the first 2n bits of the value S representing the signature of the truth table. Preferably, the present invention determines whether the inversion of a signature matches each time it determines whether the signatures of two truth tables match.
Moreover, the signatures of the truth tables may match if one or more of the inputs to one of the truth tables is inverted. Accordingly, a preferred embodiment of the present invention also determines whether the signature resulting from the inversion of one or more inputs of a truth table matches the signature of the other truth table.
Of course, the present invention preferably considers all unique permutations and inversions of inputs to a truth table when determining whether the signatures, or an inversion of one of the signatures, of the truth tables match. If the truth tables match, the matching portion of the combinatorial block can be tiled with the matching library cell and a cell or cells for performing any necessary inversions to the inputs or output.
A preferred embodiment of the present invention includes an interface to software modules for accepting a reference to a node of a Boolean tree of the combinatorial block. In addition, the software interface accepts the ordered list of the input pins to the Boolean tree. The software interface also preferably accepts a reference to the string describing the cell from the technology library.
Preferably, software modules generate the truth tables from the accepted node and string as described above. The software modules then compare the truth tables as described above and return an output indicating whether the tree can be tiled with the library cell. If the tree can be tiled with the library cell, the modules also return an ordered list of the inputs to the tree, a corresponding ordered list of inputs to the library cell also indicating whether any of the inputs are inverted, and a value indicating whether the library cell matches the Boolean tree or the inverted tree. In an alternative embodiment, the software modules do not accept a reference to the string describing the cell from the technology library. Instead, the software modules search for a matching signature from among all of the library cells.